package 单调栈;

import java.util.Deque;
import java.util.LinkedList;

//42 接雨水
public class Solution4 {
    public int trap(int[] height) {
        int res = 0;
        Deque<Integer> stack = new LinkedList();
        int last = 0;
        for(int i =0;i<height.length;i++){
            while(!stack.isEmpty()&&height[stack.getLast()]<=height[i]){
                int top = stack.pollLast();
                res+=(i-top-1)*(height[top]-height[last]);
                last = top;
            }
            if(!stack.isEmpty()){
                res+=(i-stack.getLast()-1)*(height[i]-height[last]);
                last = i;
            }
            stack.addLast(i);
        }
        return res;
    }

    //双指针
    public int trap2(int[] height) {
        int res = 0;
        int left = 0;
        int right = height.length-1;
        int leftMax = height[left];
        int rightMax = height[right];
        while(left<right){
            if(height[left]<height[right]){
                if(leftMax>height[left]) res+=leftMax-height[left];
                else leftMax = height[left];
                left++;
            }else {
                if(rightMax>height[right]) res+=rightMax-height[right];
                else rightMax = height[right];
                right--;
            }
        }
        return res;
    }
}
